package com.buaa.leecode;

import java.util.LinkedList;

/**
 * 111. Minimum Depth of Binary Tree
 */
public class N110_111 {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    int count = 0;

    private void bfsTreeNode(LinkedList<TreeNode> queue) {
        if (queue.isEmpty()) {
            return;
        }
        TreeNode top = queue.poll();
        System.out.print("," + top.val);
        int flag = 0;
        if (top.left != null) {
            queue.add(top.left);
            flag++;
        }
        if (top.right != null) {
            queue.add(top.right);
            flag++;
        }
        if (flag == 1) {
//            System.out.print(",null");
        }
        bfsTreeNode(queue);
    }


    private void print(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        bfsTreeNode(queue);
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = Integer.MAX_VALUE;
        if (root.left != null) {
            left = minDepth(root.left);
        }
        int right = Integer.MAX_VALUE;
        if (root.right != null) {
            right = minDepth(root.right);
        }
        return 1 + Math.min(left, right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = 0;
        if (root.left != null) {
            left = depth(root.left);
        }
        int right = 0;
        if (root.right != null) {
            right = depth(root.right);
        }
//        System.out.println(String.format("root=%d,left高度=%d,right高度=%d", root.val, left, right));
        if (left == Integer.MIN_VALUE || right == Integer.MIN_VALUE || Math.abs(left - right) > 1) {
            return Integer.MIN_VALUE;
        }
        return 1 + Math.max(left, right);
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int height = depth(root);
        if (height > 0) {
            return true;
        }
        return false;
    }

    TreeNode buildInput(String str) {
        TreeNode root = null, head = null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        String[] list = str.split(",");
        if (list.length > 0) {
            root = new TreeNode(Integer.parseInt(list[0]));
            queue.add(root);
        } else {
            return null;
        }
        for (int i = 1; i < list.length; i += 2) {
            head = queue.poll();
            if (!list[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(list[i]));
                head.left = left;
                queue.add(left);
            }
            if (i + 1 < list.length) {
                if (!list[i + 1].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(list[i + 1]));
                    head.right = right;
                    queue.add(right);
                }
            }
        }
        return root;
    }

    public static void main(String[] args) {
//        String input = "1,2,3,4,null,null,5,6,null,null,7";
        String input = "1,2,3,4,5,null,6,7,null,null,null,null,8";
        int[] nums = {-10, -3, 0, 5, 9};
        N110_111 solution = new N110_111();
        TreeNode root = solution.buildInput(input);
        System.out.println(solution.isBalanced(root));
    }

}
